t-distributed stochastic neighbor embedding

t-distributed stochastic neighbor embedding (t-SNE) è un algoritmo di riduzione della dimensionalità sviluppato da Geoffrey Hinton e Laurens van der Maaten, ampiamente utilizzato come strumento di apprendimento automatico in molti ambiti di ricerca.^[1]^[2]^[3]^[4]^[5]^[6]^[7] È una tecnica di riduzione della dimensionalità non lineare che si presta particolarmente all'embedding di dataset ad alta dimensionalità in uno spazio a due o tre dimensioni, nel quale possono essere visualizzati tramite un grafico di dispersione. L'algoritmo modella i punti in modo che oggetti vicini nello spazio originale risultino vicini nello spazio a dimensionalità ridotta, e oggetti lontani risultino lontani, cercando di preservare la struttura locale.

L'algoritmo si articola in due fasi principali. Nella prima fase viene costruita una distribuzione di probabilità che ad ogni coppia di punti nello spazio originale ad alta dimensionalità associa un valore di probabilità elevato se i due punti sono simili, basso se sono dissimili. Quindi viene definita una seconda distribuzione di probabilità analoga, nello spazio a dimensione ridotta. L'algoritmo quindi minimizza la divergenza di Kullback-Leibler delle due distribuzioni tramite discesa del gradiente, riorganizzando i punti nello spazio a dimensione ridotta.

Algoritmo

Dato un insieme di $N$ oggetti $\mathbf {x} _{1},\dots ,\mathbf {x} _{N}$ in uno spazio ad alta dimensionalità, t-SNE costruisce una distribuzione di probabilità $p_{ij}$ , simmetrica nelle due variabili e proporzionale alla similarità tra i punti $\mathbf {x} _{i}$ e $\mathbf {x} _{j}$ , definita come:^[8]^[1]

p_{ij}={\frac {p_{j\mid i}+p_{i\mid j}}{2N}}

dove

p_{j\mid i}={\frac {\exp(-\lVert \mathbf {x} _{i}-\mathbf {x} _{j}\rVert ^{2}/2\sigma _{i}^{2})}{\sum _{k\neq i}\exp(-\lVert \mathbf {x} _{i}-\mathbf {x} _{k}\rVert ^{2}/2\sigma _{i}^{2})}},

L'ampiezza delle gaussiane $\sigma _{i}$ è scelta in maniera tale che la perplessità della distribuzione condizionale uguagli un valore di perplessità fornito come iperparametro dell'algoritmo. In questo modo, l'ampiezza si adatta alla densità dei punti, con valori di $\sigma _{i}$ minori in aree ad alta densità.

t-SNE cerca di costruire una mappa $d$ -dimensionale $\mathbf {y} _{1},\dots ,\mathbf {y} _{N}$ (con $\mathbf {y} _{i}\in \mathbb {R} ^{d}$ ) i cui punti riflettano il meglio possibile la similarità $p_{ij}$ nello spazio di partenza. Allo scopo, la similarità $q_{ij}$ tra due punti $\mathbf {y} _{i}$ e $\mathbf {y} _{j}$ nello spazio a dimensionalità ridotta viene definita come:

q_{ij}={\frac {(1+\lVert \mathbf {y} _{i}-\mathbf {y} _{j}\rVert ^{2})^{-1}}{\sum _{k\neq m}(1+\lVert \mathbf {y} _{k}-\mathbf {y} _{m}\rVert ^{2})^{-1}}}

La differenza principale è l'uso nello spazio a dimensionalità ridotta di una distribuzione t di Student con un grado di libertà al posto della gaussiana, le cui code pesanti consentono di modellare meglio la dissimilarità tra oggetti distanti. La posizione $\mathbf {y} _{i}$ dei punti nello spazio a dimensione ridotta è quindi calcolata minimizzando tramite discesa del gradiente la divergenza di Kullback-Leibler della distribuzione $Q$ rispetto a $P$ :

KL(P||Q)=\sum _{i\neq j}p_{ij}\log {\frac {p_{ij}}{q_{ij}}}

L'uso della divergenza di Kullback-Leibler come funzione obiettivo consente di avere penalità elevate se punti vicini nello spazio originale ( $p_{ij}$ elevato) vengono considerati lontani nello spazio a dimensionalità ridotta ( $q_{ij}$ piccolo), mentre il viceversa ha un'influenza minore, tendendo quindi a preservare la struttura locale della distribuzione dei punti. Il risultato è una mappa a bassa dimensionalità che riflette le similarità tra i punti nello spazio ad alta dimensionalità.

Note

^ ^a ^b L.J.P. van der Maaten e Hinton, G.E., Visualizing High-Dimensional Data Using t-SNE (PDF), in Journal of Machine Learning Research, vol. 9, Nov 2008, pp. 2579–2605.
^ I. Gashi, Stankovic, V., Leita, C. e Thonnard, O., An Experimental Study of Diversity with Off-the-shelf AntiVirus Engines, in Proceedings of the IEEE International Symposium on Network Computing and Applications, 2009, pp. 4–11.
^ P. Hamel e Eck, D., Learning Features from Music Audio with Deep Belief Networks, in Proceedings of the International Society for Music Information Retrieval Conference, 2010, pp. 339–344.
^ A.R. Jamieson, Giger, M.L., Drukker, K., Lui, H., Yuan, Y. e Bhooshan, N., Exploring Nonlinear Feature Space Dimension Reduction and Data Representation in Breast CADx with Laplacian Eigenmaps and t-SNE, in Medical Physics, vol. 37, n. 1, 2010, pp. 339–351, DOI:10.1118/1.3267037.
^ I. Wallach e Liliean, R., The Protein-Small-Molecule Database, A Non-Redundant Structural Resource for the Analysis of Protein-Ligand Binding, in Bioinformatics, vol. 25, n. 5, 2009, pp. 615–620, DOI:10.1093/bioinformatics/btp035, PMID 19153135.
^ J. Birjandtalab, M. B. Pouyan e M. Nourani, Nonlinear dimension reduction for EEG-based epileptic seizure detection, in 2016 IEEE-EMBS International Conference on Biomedical and Health Informatics (BHI), 1º febbraio 2016, pp. 595–598, DOI:10.1109/BHI.2016.7455968.
^ Visualizing Representations: Deep Learning and Human Beings Christopher Olah's blog, 2015
^

(EN)
«The similarity of datapoint $x_{j}$ to datapoint $x_{i}$ is the conditional probability, $p_{j|i}$ , that $x_{i}$ would pick $x_{j}$ as its neighbor if neighbors were picked in proportion to their probability density under a Gaussian centered at $x_{i}$ .»

(IT)
«La similarità del punto $x_{j}$ rispetto al punto $x_{i}$ è la probabilità condizionata, $p_{j|i}$ , che $x_{i}$ scelga $x_{j}$ come suo vicino se i vicini venissero generati casualmente secondo una distribuzione di probabilità Gaussiana centrata in $x_{i}$ .»

Altri progetti

Wikimedia Commons contiene immagini o altri file sul t-distributed stochastic neighbor embedding

Collegamenti esterni

Laurens van der Maaten, t-Distributed Stochastic Neighbor Embedding, su lvdmaaten.github.io.
(EN) Implementazione di t-SNE in C++ realizzata da Laurens van der Maaten (approssimazione con il metodo di Barnes-Hut), su GitHub.
Google Tech Talk, Visualizing Data Using t-SNE, su YouTube.
(EN) Implementazione di t-SNE nel framework ELKI (approssimazione con il metodo di Barnes-Hut), su GitHub.

Portale Informatica

Portale Statistica

[MaatenHinton-1] L.J.P. van der Maaten e Hinton, G.E., Visualizing High-Dimensional Data Using t-SNE (PDF), in Journal of Machine Learning Research, vol. 9, Nov 2008, pp. 2579–2605.

[note1-2] I. Gashi, Stankovic, V., Leita, C. e Thonnard, O., An Experimental Study of Diversity with Off-the-shelf AntiVirus Engines, in Proceedings of the IEEE International Symposium on Network Computing and Applications, 2009, pp. 4–11.

[note2-3] P. Hamel e Eck, D., Learning Features from Music Audio with Deep Belief Networks, in Proceedings of the International Society for Music Information Retrieval Conference, 2010, pp. 339–344.

[note3-4] A.R. Jamieson, Giger, M.L., Drukker, K., Lui, H., Yuan, Y. e Bhooshan, N., Exploring Nonlinear Feature Space Dimension Reduction and Data Representation in Breast CADx with Laplacian Eigenmaps and t-SNE, in Medical Physics, vol. 37, n. 1, 2010, pp. 339–351, DOI:10.1118/1.3267037.

[note4-5] I. Wallach e Liliean, R., The Protein-Small-Molecule Database, A Non-Redundant Structural Resource for the Analysis of Protein-Ligand Binding, in Bioinformatics, vol. 25, n. 5, 2009, pp. 615–620, DOI:10.1093/bioinformatics/btp035, PMID 19153135.

[note5-6] J. Birjandtalab, M. B. Pouyan e M. Nourani, Nonlinear dimension reduction for EEG-based epileptic seizure detection, in 2016 IEEE-EMBS International Conference on Biomedical and Health Informatics (BHI), 1º febbraio 2016, pp. 595–598, DOI:10.1109/BHI.2016.7455968.

[note6-7] Visualizing Representations: Deep Learning and Human Beings Christopher Olah's blog, 2015

[8] 

(EN)
«The similarity of datapoint $x_{j}$ to datapoint $x_{i}$ is the conditional probability, $p_{j|i}$ , that $x_{i}$ would pick $x_{j}$ as its neighbor if neighbors were picked in proportion to their probability density under a Gaussian centered at $x_{i}$ .»

(IT)
«La similarità del punto $x_{j}$ rispetto al punto $x_{i}$ è la probabilità condizionata, $p_{j|i}$ , che $x_{i}$ scelga $x_{j}$ come suo vicino se i vicini venissero generati casualmente secondo una distribuzione di probabilità Gaussiana centrata in $x_{i}$ .»

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

V · D · M Apprendimento automatico
Problemi	Teoria dell'apprendimento statistico · Classificazione · Regressione · Regole di associazione · Apprendimento non supervisionato · Apprendimento supervisionato · Apprendimento per rinforzo · Apprendimento profondo
Apprendimento non supervisionato	Clustering · Clustering gerarchico · K-means · Algoritmo EM · DBSCAN · Mean shift · Rete generativa avversaria (cGAN · VAE-GAN · cycleGAN)
Apprendimento supervisionato	Albero di decisione · Foresta casuale · Conditional random fields CRF · Modello di Markov nascosto · K-nearest neighbors · Classificatore bayesiano · Rete neurale artificiale · Regressione lineare · Regressione logistica · Modelli grafici · Macchine a vettori di supporto
Apprendimento per rinforzo	Q-learning · SARSA · TD
Riduzione della dimensionalità	Analisi fattoriale · Analisi della correlazione canonica (CCA) · Analisi delle componenti indipendenti (ICA) · Analisi discriminante lineare (LDA) · Analisi delle componenti principali (PCA) · Selezione delle caratteristiche · Estrazione di caratteristiche · t-distributed stochastic neighbor embedding (t-SNE)
Reti neurali artificiali	Percettrone · Rete neurale a base radiale · Rete bayesiana · Rete neurale feed-forward · Rete di Hopfield · Percettrone multistrato · Rete neurale ricorrente (LSTM) · Macchina di Boltzmann ristretta · Mappa auto-organizzata · Rete neurale convoluzionale · Rete neurale a ritardo · Rete neurale spiking · Trasformatore
Software	Keras · Microsoft Cognitive Toolkit · Scikit-learn · TensorFlow · Theano · Torch · Weka
Altro	Algoritmo genetico · Particle Swarm Optimization · Caratteristica · Compromesso bias-varianza · Minimizzazione del rischio empirico

t-distributed stochastic neighbor embedding

Indice

Algoritmo

Note

Altri progetti

Collegamenti esterni

Menu di navigazione

t-distributed stochastic neighbor embedding

Algoritmo

Note

Altri progetti

Collegamenti esterni

Menu di navigazione

Ricerca